package 链表题目;

import 链表题目.model.ListNode;


// 删除链表中的重复元素2
// https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
//给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
class 删除链表中的重复元素2 {
    public ListNode deleteDuplicates1(ListNode head) {
        ListNode ans = new ListNode(0, null);
        ListNode cur = ans;
        int flag = 0;
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head = head.next;
                flag = 1;
            } else {
                if (flag == 0) {
                    ans.next = head;
                    ans = ans.next;
                    head = head.next;
                } else {
                    head = head.next;
                    flag = 0;
                }
            }
        }
        ans.next = flag == 0 ? head : null;
        return cur.next;
    }

    // 递归解法
    // 定义：输入一条单链表头结点，返回去重之后的单链表头结点
    public ListNode deleteDuplicates(ListNode head) {
        // base case
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val != head.next.val) {
            // 如果头结点和身后节点的值不同，则对之后的链表去重即可
            head.next = deleteDuplicates(head.next);
            return head;
        }
        // 如果如果头结点和身后节点的值相同，则说明从 head 开始存在若干重复节点
        // 越过重复节点，找到 head 之后那个不重复的节点
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
        }
        // 直接返回那个不重复节点开头的链表的去重结果，就把重复节点删掉了
        return deleteDuplicates(head.next);
    }

//    public static void main(String[] args) {
//        ListNode one5 = new ListNode(3, null);
//        ListNode one4 = new ListNode(3, one5);
//        ListNode one3 = new ListNode(3, one4);
//        ListNode one2 = new ListNode(2, one3);
//        ListNode one1 = new ListNode(1, one2);
//        ListNode listNode = new DeleteDuplicates2().deleteDuplicates(one1);
//    }
}
